package com.yoshino.leetcode.interview150.sliding;

import java.util.*;

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        int left = 0, sum = 0, res = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right ++) {
            sum += nums[right];
            while (sum >= target) {
                res = Math.min(right- left + 1, res);
                sum -= nums[left++];
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }

    public int lengthOfLongestSubstring(String s) {
        // 记录字符出现的位置
        int[] chars = new int[128];
        Arrays.fill(chars, -1);
        int n = s.length(), res = 0, start = 0;
        for (int i = 0; i < n; i++) {
            int ind = s.charAt(i);
            start = Math.max(start, chars[ind] + 1);
            res = Math.max(res, i - start + 1);
            chars[ind] = i;
        }
        return res;
    }

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        // 匹配单词个数
        int num = words.length;
        // 单词长度
        int wordLen = words[0].length();
        // 字符串长度
        int stringLen = s.length();

        for (int i = 0; i < wordLen; i++) {
            // 遍历的长度超过整个字符串的长度
            if (i + num * wordLen > stringLen) {
                break;
            }
            // differ表示窗口中的单词频次和words中的单词频次之差
            Map<String, Integer> differ = new HashMap<>();
            // 初始化窗口，窗口长度为num * wordLen,依次计算窗口里每个切分的单词的频次
            for (int j = 0; j < num; j++) {
                String word = s.substring(i + j * wordLen, i + (j + 1) * wordLen);
                differ.put(word, differ.getOrDefault(word, 0) + 1);
            }
            // 遍历words中的word，对窗口里每个单词计算差值
            for (String word : words) {
                differ.put(word, differ.getOrDefault(word, 0) - 1);
                // 差值为0时，移除掉这个word
                if (differ.get(word) == 0) {
                    differ.remove(word);
                }
            }
            // 开始滑动窗口
            for (int start = i; start < stringLen - num * wordLen + 1; start += wordLen) {
                if (start != i) {
                    // 右边的单词滑进来
                    String word = s.substring(start + (num - 1) * wordLen, start + num * wordLen);
                    differ.put(word, differ.getOrDefault(word, 0) + 1);
                    if (differ.get(word) == 0) {
                        differ.remove(word);
                    }
                    // 左边的单词滑出去
                    word = s.substring(start - wordLen, start);
                    differ.put(word, differ.getOrDefault(word, 0) - 1);
                    if (differ.get(word) == 0) {
                        differ.remove(word);
                    }
                }
                // 窗口匹配的单词数等于words中对应的单词数
                if (differ.isEmpty()) {
                    res.add(start);
                }
            }
        }
        return res;
    }

    Map<Character, Integer> ori = new HashMap<>();
    Map<Character, Integer> cur = new HashMap<>();

    public String minWindow(String s, String t) {
        if (t.length() > s.length()) {
            return "";
        }
        int tLen = t.length();
        Character c;
        for (int i = 0; i < tLen; i++) {
            c = t.charAt(i);
            ori.put(c, ori.getOrDefault(c, 0) + 1);
        }
        int l = 0, r = -1, sLen = s.length(), len = Integer.MAX_VALUE, resL = -1, resR = -1;
        while (r < sLen) {
            r++;
            if (r < sLen && ori.containsKey(s.charAt(r))) {
                cur.put(s.charAt(r), cur.getOrDefault(s.charAt(r), 0) + 1);
            }
            while (check() && l <= r) {
                if (r - l + 1 < len) {
                    len = r - l + 1;
                    resL = l;
                    resR = l + len;
                }
                if (ori.containsKey(s.charAt(l))) {
                    cur.put(s.charAt(l), cur.getOrDefault(s.charAt(l), 0) - 1);
                }
                l++;
            }
        }
        return resL == -1 ? "" : s.substring(resL, resR);
    }

    private boolean check() {
        Iterator<Map.Entry<Character, Integer>> iterator = ori.entrySet().iterator();
        while (iterator.hasNext()) {
            Map.Entry<Character, Integer> entry = iterator.next();
            if (cur.getOrDefault(entry.getKey(), 0) < entry.getValue()) {
                return false;
            }
        }
        return true;
    }

}